package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC39 {
    private final List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        traceBack(candidates,0,0,target,new ArrayList<>());
        return ans;
    }
    public void traceBack(int[] candidates, int index, int sum ,int target, List<Integer> list){
        if(sum == target){
            ans.add(new ArrayList<>(list));
            return;
        }
        for(int i = index; i<candidates.length;i++){
            if(sum>target) break;
            list.add(candidates[i]);
            traceBack(candidates,i,sum+candidates[i],target,list);
            list.remove(list.size()-1);
        }
    }
}
